package offer;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@FunctionalInterface
public interface FindSubstring {
    List<Integer> findSubstring(String s, String[] words);
}
class FindSubStringImpl1 implements  FindSubstring{
    static final String TEST_01_S = "barfoothefoobarman";
    static final String[] TEST_01_WORDS = new String[]{"foo","bar"};
    static final String TEST_02_S = "wordgoodgoodgoodbestword";
    static final String[] TEST_02_WORDS = new String[]{"word","good","best","good"};
    public static void main(String[] args) {
        new FindSubStringImpl1().findSubstring(TEST_01_S,TEST_01_WORDS);
        new FindSubStringImpl1().findSubstring(TEST_02_S,TEST_02_WORDS);
    }

    /**
     * 暴力穷举，字符串中每一个字符都需要遍历一遍，外层o(n),内层循环对子字符数组进行了一次排序，字符数组元素数量为 k ,需要klogk的时间
     * 子字符最多可以有模板字符串的那么长，否则一定不匹配
     * 则时间复杂度为 o(n^2 logn)
     * @param s
     * @param words
     * @return
     */
    @Override
    public List<Integer> findSubstring(String s, String[] words) {
        if(words.length == 0){
            return new ArrayList<>();
        }
        Arrays.sort(words);
        List<Integer> ans = new ArrayList<>();
        int wordNums = words.length;
        int wordLen = words[0].length();
        int subStringOffset = wordLen * wordNums;
        for (int i = 0; i <= s.length() - subStringOffset; i++) {
            String subStr = s.substring(i, subStringOffset + i);
            boolean valid = true;
            String[] curSubStrs = new String[wordNums];
            for (int j = 0; j < wordNums; j++) {
                int start = j * wordLen;
                int end = (j + 1) * wordLen;
                curSubStrs[j] = subStr.substring(start,end);
            }
            Arrays.sort(curSubStrs);
            for (int j = 0; j < wordNums; j++) {
                if(!curSubStrs[j].equals(words[j])){
                    valid = false;
                }
            }
            if(valid){
                ans.add(i);
            }
        }
        return ans;
    }
}
class FindSubstringImpl2 implements FindSubstring{

    @Override
    public List<Integer> findSubstring(String s, String[] words) {
        return null;
    }
}